# 全排列 回溯


class Solution:

    def permute(self, nums:list[int]) -> list[list[int]]:
        # 长度为1的情况
        if len(nums) == 1:
            return [nums]
        

        def dfs(x):
            # 固定到最后一层
            if x == len(nums) - 1:
                res.append(list(nums))
                return
            
            for i in range(x, len(nums)):
                nums[i], nums[x] = nums[x], nums[i]
                dfs(x+1)
                # 恢复交换
                nums[i], nums[x] = nums[x], nums[i]
            



        res = []
        dfs(0)

        return res
        




if __name__ == "__main__":
    a = [1,2,3]
    res = Solution().permute(a)
    print(res)

